Search Results

Documents authored by Angluin, Dana

Document
DOI: 10.4230/LIPIcs.CSL.2020.8
Strongly Unambiguous Büchi Automata Are Polynomially Predictable With Membership Queries

Authors: Dana Angluin, Timos Antonopoulos, and Dana Fisman

Published in: LIPIcs, Volume 152, 28th EACSL Annual Conference on Computer Science Logic (CSL 2020)

Abstract
A Büchi automaton is strongly unambiguous if every word w ∈ Σ^ω has at most one final path. Many properties of strongly unambiguous Büchi automata (SUBAs) are known. They are fully expressive: every regular ω-language can be represented by a SUBA. Equivalence and containment of SUBAs can be decided in polynomial time. SUBAs may be exponentially smaller than deterministic Muller automata and may be exponentially bigger than deterministic Büchi automata. In this work we show that SUBAs can be learned in polynomial time using membership and certain non-proper equivalence queries, which implies that they are polynomially predictable with membership queries. In contrast, under plausible cryptographic assumptions, non-deterministic Büchi automata are not polynomially predictable with membership queries.
Cite as

Dana Angluin, Timos Antonopoulos, and Dana Fisman. Strongly Unambiguous Büchi Automata Are Polynomially Predictable With Membership Queries. In 28th EACSL Annual Conference on Computer Science Logic (CSL 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 152, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{angluin_et_al:LIPIcs.CSL.2020.8,
  author =	{Angluin, Dana and Antonopoulos, Timos and Fisman, Dana},
  title =	{{Strongly Unambiguous B\"{u}chi Automata Are Polynomially Predictable With Membership Queries}},
  booktitle =	{28th EACSL Annual Conference on Computer Science Logic (CSL 2020)},
  pages =	{8:1--8:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-132-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{152},
  editor =	{Fern\'{a}ndez, Maribel and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2020.8},
  URN =		{urn:nbn:de:0030-drops-116519},
  doi =		{10.4230/LIPIcs.CSL.2020.8},
  annote =	{Keywords: Polynomially predictable languages, Automata learning, Strongly unambiguous B\"{u}chi automata, Automata succinctness, Regular \omega-languages, Grammatical inference}
}
Document
DOI: 10.4230/LIPIcs.CSL.2017.10
Query Learning of Derived Omega-Tree Languages in Polynomial Time

Authors: Dana Angluin, Timos Antonopoulos, and Dana Fisman

Published in: LIPIcs, Volume 82, 26th EACSL Annual Conference on Computer Science Logic (CSL 2017)

Abstract
We present the first polynomial time algorithm to learn nontrivial classes of languages of infinite trees. Specifically, our algorithm uses membership and equivalence queries to learn classes of omega-tree languages derived from weak regular omega-word languages in polynomial time. The method is a general polynomial time reduction of learning a class of derived omega-tree languages to learning the underlying class of omega-word languages, for any class of omega-word languages recognized by a deterministic Büchi acceptor. Our reduction, combined with the polynomial time learning algorithm of Maler and Pnueli [Maler and Pneuli, Inform. Comput., 1995] for the class of weak regular omega-word languages yields the main result. We also show that subset queries that return counterexamples can be implemented in polynomial time using subset queries that return no counterexamples for deterministic or non-deterministic finite word acceptors, and deterministic or non-deterministic Büchi omega-word acceptors. A previous claim of an algorithm to learn regular omega-trees due to Jayasrirani, Begam and Thomas [Jayasrirani et al., ICGI, 2008] is unfortunately incorrect, as shown in [Angluin, YALEU/DCS/TR-1528, 2016].
Cite as

Dana Angluin, Timos Antonopoulos, and Dana Fisman. Query Learning of Derived Omega-Tree Languages in Polynomial Time. In 26th EACSL Annual Conference on Computer Science Logic (CSL 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 82, pp. 10:1-10:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{angluin_et_al:LIPIcs.CSL.2017.10,
  author =	{Angluin, Dana and Antonopoulos, Timos and Fisman, Dana},
  title =	{{Query Learning of Derived Omega-Tree Languages in Polynomial Time}},
  booktitle =	{26th EACSL Annual Conference on Computer Science Logic (CSL 2017)},
  pages =	{10:1--10:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-045-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{82},
  editor =	{Goranko, Valentin and Dam, Mads},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2017.10},
  URN =		{urn:nbn:de:0030-drops-77022},
  doi =		{10.4230/LIPIcs.CSL.2017.10},
  annote =	{Keywords: Learning, queries, infinite trees, derived tree languages, reactive systems}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.11
Families of DFAs as Acceptors of omega-Regular Languages

Authors: Dana Angluin, Udi Boker, and Dana Fisman

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
Families of DFAs (FDFAs) provide an alternative formalism for recognizing omega-regular languages. The motivation for introducing them was a desired correlation between the automaton states and right congruence relations, in a manner similar to the Myhill-Nerode theorem for regular languages. This correlation is beneficial for learning algorithms, and indeed it was recently shown that omega-regular languages can be learned from membership and equivalence queries, using FDFAs as the acceptors. In this paper, we look into the question of how suitable FDFAs are for defining omega-regular languages. Specifically, we look into the complexity of performing Boolean operations, such as complementation and intersection, on FDFAs, the complexity of solving decision problems, such as emptiness and language containment, and the succinctness of FDFAs compared to standard deterministic and nondeterministic omega-automata. We show that FDFAs enjoy the benefits of deterministic automata with respect to Boolean operations and decision problems. Namely, they can all be performed in nondeterministic logarithmic space. We provide polynomial translations of deterministic Buchi and coBuchi automata to FDFAs and of FDFAs to nondeterministic Buchi automata (NBAs). We show that translation of an NBA to an FDFA may involve an exponential blowup. Last, we show that FDFAs are more succinct than deterministic parity automata (DPAs) in the sense that translating a DPA to an FDFA can always be done with only a polynomial increase, yet the other direction involves an inevitable exponential blowup in the worst case.
Cite as

Dana Angluin, Udi Boker, and Dana Fisman. Families of DFAs as Acceptors of omega-Regular Languages. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{angluin_et_al:LIPIcs.MFCS.2016.11,
  author =	{Angluin, Dana and Boker, Udi and Fisman, Dana},
  title =	{{Families of DFAs as Acceptors of omega-Regular Languages}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{11:1--11:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.11},
  URN =		{urn:nbn:de:0030-drops-64274},
  doi =		{10.4230/LIPIcs.MFCS.2016.11},
  annote =	{Keywords: finite automata, omega regular languages}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact